package sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

public class ShellSort {

    public static void main(String[] args) {
        int arr[] = new int[8000000];
        for (int i = 0; i < 8000000; i++){
            arr[i] = (int)(Math.random() * 800000);
        }
//        int arr[] = new int[]{6,3,8,7,1,0};

        Date date1 = new Date();
        SimpleDateFormat sim = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String date1Str = sim.format(date1);
        System.out.println("排序前的时间:"+date1Str);
        ShellSort2(arr);
        Date date2 = new Date();
        String date2Str = sim.format(date2);
        System.out.println("排序后的时间:"+date2Str);


    }

    public static void ShellSort(int[] arr){
//        //第一轮
//        //第一轮排序分成了5组
//        int temp;
//        for (int i = 5; i < arr.length; i++){
//            //遍历各组中所有的元素(共五组，每组两个元素 )
//            for (int j = i - 5;j >= 0; j-=5){
//                //如果当前元素大于加上步长后的元素，就变替位置
//                if (arr[j] > arr[j + 5]){
//                    temp = arr[j];
//                    arr[j] = arr[j + 5];
//                    arr[j + 5] = temp;
//                }
//            }
//        }
//        System.out.println("排序后："+Arrays.toString(arr));
//        for (int i = 2; i < arr.length; i++){
//            //遍历各组中所有的元素(共五组，每组两个元素 )
//            for (int j = i - 2; j >= 0; j-=2){
//                //如果当前元素大于加上步长后的元素，就变替位置
//                if (arr[j] > arr[j + 2]){
//                    temp = arr[j];
//                    arr[j] = arr[j + 2];
//                    arr[j + 2] = temp;
//                }
//            }
//        }
//        System.out.println("排序后："+Arrays.toString(arr));
//        for (int i = 1; i < arr.length; i++){
//            //遍历各组中所有的元素(共五组，每组两个元素 )
//            for (int j = i - 1; j >= 0; j-=1){
//                //如果当前元素大于加上步长后的元素，就变替位置
//                if (arr[j] > arr[j + 1]){
//                    temp = arr[j];
//                    arr[j] = arr[j + 1];
//                    arr[j + 1] = temp;
//                }
//            }
//        }
//        System.out.println("排序后："+Arrays.toString(arr));
        int temp;
        for (int gap = arr.length / 2; gap > 0; gap /= 2){
            for (int i = gap; i < arr.length; i++){
                for (int j = i - gap; j >= 0; j-=gap){
                    if (arr[j] > arr[j + gap]){
                        temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
        }
//        System.out.println("排序后："+Arrays.toString(arr));

    }

    //对上方交换式的希尔算法转变为移动法
    public static void ShellSort2(int[] arr){
//        int j;
//        int temp;
        for (int gap = arr.length / 2; gap > 0; gap /= 2){
            //从第gap元素，逐个对其所在的组进行直接插入排序
            for (int i = gap; i < arr.length; i++){
                int j = i;
                int temp = arr[j];
                while (j - gap >= 0 && temp < arr[j - gap]){
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = temp;
            }
        }
    }
}
